package SortedLinkList;

/**
 * Created by sunwei on 2017/10/10
 * Time:13:52
 */
public class SortedList {
    private Link first;

    public SortedList() {
        first = null;
    }

    public boolean isEmpty(){
        return (first==null);
    }
    /*
    在链表里面插入元素，这个元素在插入的时候就会按照从小到大的顺序排序好
     */
    public void insert(long key){
        Link newLink = new Link(key);
        Link previous = null;
        Link current = first;
        //这个循环的目的就是搜索正确的插入点，找一下应该放在哪个位置，循环后就找到了这个适当的位置，这个循环跳出的
        //条件就是：current为null或者key<current.data，这两个条件都会跳出循环。
        while (current!=null&&key>current.dData){//如果当前的节点不是空，并且插入的数据比当前的节点数据值大
            previous = current;//往后移动标记
            current = current.next;//当前的节点记号也要往后移动
        }
        //while循环结束后这个需要插入的位置，可能在链表头、或者表中、或者在表尾，
        // 如果current在表头或者链表为空previous将为null,这个时候可以让first指向新的节点，否则current就在表中和表尾
        if (previous==null) {  //如果previous为null则说明，没有进入循环，则说明插入的数据比原来链表中的数据都要小，所以应该放在第一个位置
              first = newLink;
        }else {
            //排除特殊情况后，则将新实例化的链表放到链表节点里面去
            previous.next = newLink;
        }
            newLink.next = current;

    }
    /*
    删除有序链表的节点
     */
    public Link remove(){
        Link temp = first;
        first = first.next;
        return temp;
    }
    /*
    遍历显示节点
     */
    public void displayList(){
        System.out.print("List(first-->last): ");
        Link current = first;
        while (current!=null){
            current.displayLink();
            current = current.next;
        }
        System.out.println(" ");
    }

}
